#include<iostream>
#include<queue>
#include<vector>

using namespace std;

//BFS解决floodfill01：图像渲染
class Solution1 {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        int init=image[sr][sc];
        if(init==color) return image;
        queue<vector<int>> q;
        q.push({sr,sc});
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        int m=image.size();int n=image[0].size();
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                auto top=q.front();
                image[top[0]][top[1]]=color;
                q.pop();
                for(int j=0;j<4;j++)
                {
                    int x=top[0]+dx[j];
                    int y=top[1]+dy[j];
                    if(x>=0&&y>=0&x<m&&y<n&&image[x][y]==init)
                    {
                        q.push({x,y});
                    }
                }
            }
        }
        return image;
    }
};

//BFS解决floodfill02：岛屿数量
class Solution2 {
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        bool check[301][301]={};
        int ret=0;
        int m=grid.size();int n=grid[0].size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1'&&check[i][j]==false)
                {
                    queue<vector<int>>  q;
                    check[i][j]=true;
                    q.push({i,j});
                    while(!q.empty())
                    {
                        int size=q.size();
                        for(int k=0;k<size;k++)
                        {
                            auto top=q.front();
                            q.pop();
                            for(int h=0;h<4;h++)
                            {
                                int x=top[0]+dx[h];
                                int y=top[1]+dy[h];
                                if(x>=0&&y>=0&x<m&&y<n&&grid[x][y]=='1'&&check[x][y]==false)
                                {
                                    check[x][y]=true;
                                    q.push({x,y});
                                }
                            }
                        }
                    }
                    //cout<<i<<":"<<j<<" ";
                    ret++;
                }
            }
        }
        return ret;
    }
};

//BFS解决floodfill03：岛屿的最大面积
class Solution3 {
private:
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
    bool check[51][51]={};

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int m=grid.size();int n=grid[0].size();
        int ret=0;
        queue<vector<int>>  q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1&&check[i][j]==false)
                {
                    int path=1;
                    check[i][j]=true;
                    q.push({i,j});
                    while(!q.empty())
                    {
                        int size=q.size();
                        for(int k=0;k<size;k++)
                        {
                            auto top=q.front();
                            q.pop();
                            for(int h=0;h<4;h++)
                            {
                                int x=top[0]+dx[h];
                                int y=top[1]+dy[h];
                                if(x>=0&&y>=0&&y<n&&x<m&&check[x][y]==false&&grid[x][y]==1)
                                {
                                    q.push({x,y});
                                    check[x][y]=true;
                                    cout<<
                                    path++;
                                }
                            }
                        }
                    }
                    ret=path>ret?path:ret;
                }
            }
        }
        return ret;
    }
};


//BFS解决floodfill04：被围绕的区域
class Solution4 {
public:
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) {
            return;
        }
        int n = board[0].size();
        queue<pair<int, int>> que;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                que.emplace(i, 0);
                board[i][0] = 'A';
            }
            if (board[i][n - 1] == 'O') {
                que.emplace(i, n - 1);
                board[i][n - 1] = 'A';
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (board[0][i] == 'O') {
                que.emplace(0, i);
                board[0][i] = 'A';
            }
            if (board[m - 1][i] == 'O') {
                que.emplace(m - 1, i);
                board[m - 1][i] = 'A';
            }
        }
        while (!que.empty()) {
            int x = que.front().first, y = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx < 0 || my < 0 || mx >= m || my >= n || board[mx][my] != 'O') {
                    continue;
                }
                que.emplace(mx, my);
                board[mx][my] = 'A';
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
};


int main()
{
    return 0;
}
